Linked List

A linked list is a fundamental data structure that represents a sequence of elements. Each element, known as a node, contains:

• Data (Value): The information stored in the node.
• Reference (Pointer): A link to the next node in the sequence.

The first node is called the head, and the last node is the tail, which points to None, indicating the end of the list.

Node Structure in Python

Here's an example of a simple node class for a singly linked list:

class ListNode:
    """Node class for a singly linked list."""
    def __init__(self, val: int):
        self.val: int = val          # Data stored in the node
        self.next: 'ListNode' = None # Reference to the next node

Creating a Linked List

To build a linked list, instantiate nodes and link them using their next references:

# Create nodes with values
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)

# Link nodes: 1 -> 3 -> 2 -> 5 -> 4
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

# Set the head of the list
head = n0

Common Operations on Linked Lists

Time Complexity Comparison

Operation	Array	Singly Linked List	Doubly Linked List	Circular Linked List
Access by Index	O (1)	O (n)	O (n)	O (n)
Insertion at Head	O (n)	O (1)	O (1)	O (1)
Deletion at Head	O (n)	O (1)	O (1)	O (1)
Insertion at Tail	O (1)*	O (n)**	O (1)	O (1)
Deletion at Tail	O (1)*	O (n)	O (1)	O (1)
Search by Value	O (n)	O (n)	O (n)	O (n)

* If the array has unused capacity at the end.

** O (1) if a tail reference is maintained.

Inserting a Node

To insert a node P after a node n0:

def insert(n0: ListNode, P: ListNode):
    """Insert node P after node n0 in the linked list."""
    P.next = n0.next
    n0.next = P

Deleting a Node

To remove the node immediately after n0:

def remove(n0: ListNode):
    """Remove the node after node n0 in the linked list."""
    if n0.next:
        n0.next = n0.next.next

Accessing a Node by Index

To access the node at a specific index:

def access(head: ListNode, index: int) -> ListNode | None:
    """Return the node at the specified index."""
    current = head
    for _ in range(index):
        if current is None:
            return None
        current = current.next
    return current

Searching for a Node by Value

To find the first node with a given value:

def find(head: ListNode, target: int) -> int:
    """Return the index of the node with the target value."""
    current = head
    index = 0
    while current:
        if current.val == target:
            return index
        current = current.next
        index += 1
    return -1  # Target not found

Arrays vs. Linked Lists

Key Differences

Feature	Arrays	Linked Lists
Memory Allocation	Contiguous	Non-contiguous
Size	Fixed (static)	Dynamic
Memory Overhead	Minimal	Extra for pointers
Access Time	O (1) (random access)	O (n) (sequential access)
Insertion/Deletion	O (n) (requires shifting)	O (1) (if node is known)
Cache Performance	Better (due to locality)	Poorer

Types of Linked Lists

Singly Linked List

• Structure: Nodes with a single next reference.
• Traversal: Forward only.

Doubly Linked List

• Structure: Nodes with next and prev references.

• Traversal: Forward and backward.

• Node Class Example:

  class ListNode:
      """Node class for a doubly linked list."""
      def __init__(self, val: int):
          self.val: int = val
          self.next: 'ListNode' = None
          self.prev: 'ListNode' = None

Circular Linked List

• Structure: The last node points back to the first node.
• Use Cases: Useful for applications requiring cyclic traversal.

Advantages and Disadvantages

Advantages

• Dynamic Size: Adjusts during runtime as elements are added or removed.
• Efficient Insertions/Deletions: O (1) time when inserting or deleting at known positions.
• Flexible Memory Use: Utilizes memory as needed without pre-allocation.

Disadvantages

• Memory Overhead: Additional memory for storing references.
• No Random Access: Cannot directly access elements by index.
• Cache Inefficiency: Non-contiguous memory allocation can lead to cache misses.
• Complexity: More complex implementation compared to arrays.

Applications of Linked Lists

Singly Linked Lists

• Stacks and Queues: Implementing LIFO and FIFO structures.
• Hash Tables: Handling collisions using chaining.
• Adjacency Lists: Representing sparse graphs.

Doubly Linked Lists

• LRU Caches: Efficiently updating and accessing recently used items.
• Text Editors: Managing the sequence of characters for efficient insertions and deletions.
• Browser Navigation: Implementing back and forward navigation.

Circular Linked Lists

• Round-Robin Scheduling: Distributing resources evenly across processes.
• Audio/Video Buffers: Implementing continuous playback loops.
• Multiplayer Games: Managing players in turn-based games.